package com.lw.leetcode.bit.b;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 2438. 二的幂数组中查询范围内的乘积
 *
 * @author liw
 * @version 1.0
 * @date 2022/10/17 11:02
 */
public class ProductQueries {

    public static void main(String[] args) {
        ProductQueries test = new ProductQueries();

        // [2,4,64]
//        int n = 15;
//        int[][] arr = {{0, 1}, {2, 2}, {0, 3}};

        // [256,128,2,4194304,16777216,512,131072,128,256,131072,8,524288,268435456,256,128,2,8192,32768,128,131072,16384,16,16384,4194304,128,256,16777216,32768,16384,512,512,512,4,4194304,16384,128,8192,256,512,4,64,256,147483634,16,512,128,1,8,512,512,268435456,16384,512,4,16777216]
        int n = 806335498;
        int[][] arr = {{5, 5}, {4, 4}, {0, 1}, {1, 5}, {4, 6}, {6, 6}, {5, 6}, {0, 3}, {5, 5}, {5, 6}, {1, 2}, {3, 5}, {3, 6}, {5, 5}, {4, 4}, {1, 1}, {2, 4}, {4, 5}, {4, 4}, {5, 6}, {0, 4}, {3, 3}, {0, 4}, {0, 5}, {4, 4}, {5, 5}, {4, 6}, {4, 5}, {0, 4}, {6, 6}, {6, 6}, {6, 6}, {2, 2}, {0, 5}, {1, 4}, {0, 3}, {2, 4}, {5, 5}, {6, 6}, {2, 2}, {2, 3}, {5, 5}, {0, 6}, {3, 3}, {6, 6}, {4, 4}, {0, 0}, {0, 2}, {6, 6}, {6, 6}, {3, 6}, {0, 4}, {6, 6}, {2, 2}, {4, 6}};

        // [2]
//        int n = 2;
//        int[][] arr = {{0, 0}};

        // [8,8,8,4,4,4,4,8,4]
//        int n = 6;
//        int[][] arr = {{0,1},{0,1},{0,1},{1,1},{1,1},{1,1},{1,1},{0,1},{1,1}};

        int[] ints = test.productQueries(n, arr);
        System.out.println(Arrays.toString(ints));
    }

    public int[] productQueries(int n, int[][] queries) {
        long[] item = new long[32];
        int index = 0;
        long t = 1;
        item[0] = 1;
        while (n != 0) {
            if ((n & 1) != 0) {
                item[index++] = t;
            }
            n >>= 1;
            t <<= 1;
        }
        int size = queries.length;
        int[] values = new int[size];
        for (int i = 0; i < size; i++) {
            int[] query = queries[i];
            int b = query[1];
            t = 1;
            for (int j = query[0]; j <= b ; j++) {
                t = t * item[j] % 1000000007;
            }
            values[i] = (int) t;
        }
        return values;
    }

}
